package B刷题.暴力递归.A回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @author wei.zhao
 * @description: LeetCode301.删除无效的括号
 * @date 2022年04月10日 12:14
 */
public class Code07_RemoveInvalidParentheses {

    /**
     * 思路：
     * 计算无效的左、右括号；
     * 当无效的左、右括号数都为0，判断是否有效，有效则返回，否则返回空；
     * 当前位置的字符是左、右括号，且左右括号的无效数不等于0，则尝试删除该字符；
     * 剪枝：
     * 当前字符如果不是左、右括号或者对应的无效数等于0，就没必要尝试删除了。
     * 防止重复：
     * 前一个字符跟当前字符是一样的，删除哪一个都一样，前面一个已经试过了，所以当前这个跳过；
     * 先删第一个、再删第N个，与先删第N个、再删第一个，是一样的，所以只能往后删。
     */
    public static final char left = '(';
    public static final char right = ')';

    public List<String> result = new ArrayList<>();

    public List<String> removeInvalidParentheses(String s) {
        //计算无效的左、右括号
        int[] countInvalid = countInvalid(s);
        process(s, countInvalid[0], countInvalid[1], 0);
        return result;
    }

    private void process(String s, int leftInvalid, int rightInvalid, int start) {
        if (leftInvalid + rightInvalid == 0) {
            if (isValid(s)) {
                result.add(s);
            }
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if ((i != 0 && s.charAt(i) == s.charAt(i - 1))) {
                continue;
            }
            if (s.charAt(i) == left && leftInvalid != 0) {
                process(s.substring(0, i) + s.substring(i + 1), leftInvalid - 1, rightInvalid, i);
            }
            if (s.charAt(i) == right && rightInvalid != 0) {
                process(s.substring(0, i) + s.substring(i + 1), leftInvalid, rightInvalid - 1, i);
            }
        }
    }

    public int[] countInvalid(String s) {
        int[] result = new int[2];
        int leftInvalid = 0;
        int rightInvalid = 0;
        for (char aChar : s.toCharArray()) {
            if (aChar == left) {
                leftInvalid++;
            } else if (aChar == right) {
                if (leftInvalid != 0) {
                    leftInvalid--;
                } else {
                    rightInvalid++;
                }
            }
        }
        result[0] = leftInvalid;
        result[1] = rightInvalid;
        return result;
    }

    public boolean isValid(String s) {
        int leftTotal = 0;
        for (char aChar : s.toCharArray()) {
            if (aChar == left) {
                leftTotal++;
            } else if (aChar == right) {
                if (leftTotal == 0) {
                    return false;
                } else {
                    leftTotal--;
                }
            }
        }
        return leftTotal == 0;
    }

}
